//给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
//
// 有效 二叉搜索树定义如下：
//
//
// 节点的左子树只包含 小于 当前节点的数。
// 节点的右子树只包含 大于 当前节点的数。
// 所有左子树和右子树自身必须也是二叉搜索树。
//
//
//
//
// 示例 1：
//
//
//输入：root = [2,1,3]
//输出：true
//
//
// 示例 2：
//
//
//输入：root = [5,1,4,null,null,3,6]
//输出：false
//解释：根节点的值是 5 ，但是右子节点的值是 4 。
//
//
//
//
// 提示：
//
//
// 树中节点数目范围在[1, 10⁴] 内
// -2³¹ <= Node.val <= 2³¹ - 1
//
//
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 👍 1943 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

/*
        5
      4   6
         3  7
 */
//? 二叉搜索树的中序遍历是有序的 申请辅助数组
function isValidBST(root: TreeNode | null): boolean {

    const traversalArr: number[] = [];
    function inorderTraverse(root: TreeNode | null): void {
        if (root === null) return;
        inorderTraverse(root.left);
        traversalArr.push(root.val);
        inorderTraverse(root.right);
    }
    inorderTraverse(root);
    for (let i = 0, length = traversalArr.length; i < length - 1; i++) {
        if (traversalArr[i] >= traversalArr[i + 1]) return false;
    }
    return true;

};
//leetcode submit region end(Prohibit modification and deletion)
//? 递归中解决
function isValidBST2(root: TreeNode | null): boolean {
    let maxVal = -Infinity;
    function inorderTraverse(root: TreeNode | null): boolean {
        if (root === null) return true;
        let leftValid: boolean = inorderTraverse(root.left);
        if (!leftValid) return false;
        if (maxVal < root.val) {
            maxVal = root.val
        } else {
            return false;
        }
        let rightValid: boolean = inorderTraverse(root.right);
        return leftValid && rightValid;
    }
    return inorderTraverse(root);
};
